/*
 * Copyright (c) 2008, Justin Choy
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1) Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer.
 * 
 * 2) Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution.
 * 
 * 3) Neither the name of the owner nor the names of its contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
package data;

import error.InvalidValueException;
import error.ProgrammingErrorException;
import error.Severity;

/**
 * @author jchoy
 *
 */
public class BinaryTree <T extends Comparable<T>>{
    
    private Node<T> rootNode = null;
    private static final int LESSER_CHILD_NODE_INDEX = 0;
    private static final int GREATER_CHILD_NODE_INDEX = 1;
    private static final int DATA_OBJECT_INDEX = 0;
    private static final int NUM_DATA_OBJECTS = 1;
    private static final int NUM_CHILD_NODES = 2;
    private static final int CHILD_NODE_INDECES[] 
                        = { LESSER_CHILD_NODE_INDEX, GREATER_CHILD_NODE_INDEX };
    
    
    /**
     * Adds a data object to the binary tree
     * 
     * @param dataObject The data object to add
     * @throws InvalidValueException if the dataObject is null or duplicate
     * @throws ProgrammingErrorException
     */
    public void addDataObject( T dataObject )
    throws InvalidValueException, ProgrammingErrorException {
        
        if ( dataObject  == null ) {
            String errMsg = "null Data Objects are not allowed!";
            throw new InvalidValueException( Severity.NON_FATAL, errMsg );
        }
        
        // Create the new Node to add to the tree and set the data object
        Node<T> newNode = new Node<T>(NUM_DATA_OBJECTS, NUM_CHILD_NODES);
        newNode.setDataObject( DATA_OBJECT_INDEX, dataObject );
        
        // Check if we have a root node. If not, set it to newNode and exit
        if (rootNode == null) {
            rootNode = newNode;    
            return;
        }
        
        // If we do have a root node, the find where we should put the new node
        Node<T> currentNode = rootNode;
        T currentNodeObject = null;
        int indexToWrite = -1;
        int compareResult = 0;
        
        while ( true ) {
            currentNodeObject = currentNode.getDataObject(DATA_OBJECT_INDEX);
            
            compareResult = dataObject.compareTo( currentNodeObject );
            
            /* If the object is less than the currentNodeObject */
            if ( compareResult < 0 ) {
                indexToWrite = LESSER_CHILD_NODE_INDEX;
                
            /* If the object is greater than the currentNodeObject */
            } else if ( compareResult > 0 ) {
                indexToWrite = GREATER_CHILD_NODE_INDEX;
                
            /* If the object is equal to the currentNodeObject */
            } else {
                String errMsg = "Duplicate Objects are not allowed!";
                throw new InvalidValueException( Severity.NON_FATAL, errMsg );
            }
            
            
            if ( currentNode.getChildNode( indexToWrite ) == null ) {
                break;
            } else {
                currentNode = currentNode.getChildNode( indexToWrite );
            }
            
        }
        
        currentNode.setChildNode( indexToWrite, newNode );
        newNode.setParentNode( currentNode );
    }
    
    /**
     * Finds the node that contains the key of dataObject
     * @param dataObject An object with the same key to find in the tree
     * @return The object that has the same key as dataObject. null if not
     * found.
     * @throws InvalidValueException if the dataObject is null.
     */
    private Node<T> findNode( T dataObject ) throws InvalidValueException {
        
        Node<T> currentNode = rootNode;
        T currentNodeObject = null;
        int compareResult = 0;
        
        if ( dataObject == null ) {
            String errMsg = "null data objects are not allowed in this tree!";
            throw new InvalidValueException( Severity.NON_FATAL, errMsg );
        }
        
        while ( currentNode != null ) {
            currentNodeObject = currentNode.getDataObject(DATA_OBJECT_INDEX);
            compareResult = dataObject.compareTo( currentNodeObject );

            /* If the object is less than the currentNodeObject */
            if ( compareResult < 0 ) {
                currentNode 
                = currentNode.getChildNode( LESSER_CHILD_NODE_INDEX );

                /* If the object is greater than the currentNodeObject */
            } else if ( compareResult > 0 ) {
                currentNode
                = currentNode.getChildNode( GREATER_CHILD_NODE_INDEX);

                /* If the object is equal to the currentNodeObject */
            } else {
                break;
            }
        }
        
        return currentNode;
    }
    
    /**
     * Retrieves the data object in the tree using the Comparable.compareTo
     * method. Ideally you should construct a new dataObject with the key
     * you are trying to find to get the dataObject in this tree with the same
     * key.
     * 
     * @param dataObject A dataObject with the same key as the object you are
     * trying to find.
     * @return The dataObject in this tree with the same key as the parameter
     * dataObject. If there is no dataObject with the same key, return null.
     * @throws InvalidValueException if the dataObject is null or not found.
     */
    public T getDataObject( T dataObject ) throws InvalidValueException {
        Node<T> node = findNode( dataObject );
        
        if ( node == null ) {
            String errMsg = "The data object was not found in the tree.";
            throw new InvalidValueException( Severity.NON_FATAL, errMsg );
        }
        
        return node.getDataObject(DATA_OBJECT_INDEX);
    }
    
    /**
     * Finds the successor node by traversing the tree and searching for the
     * next highest key value node. Also replaces the node with its right child
     * if it exists.
     * @param node The node we are trying to find the successor of
     * @return The successor node of node
     */
    private Node<T> getSuccessorNode( Node<T> node ) {
        Node<T> currentNode = node;
        Node<T> nextNode = currentNode.getChildNode( GREATER_CHILD_NODE_INDEX );
        
        while ( nextNode != null ) {
            currentNode = nextNode;
            nextNode = nextNode.getChildNode( LESSER_CHILD_NODE_INDEX );
        }
        
        if ( currentNode.getChildNode( GREATER_CHILD_NODE_INDEX ) != null ) {
            replaceChildNode( currentNode,
                        currentNode.getChildNode( GREATER_CHILD_NODE_INDEX ) );
        }
        
        return currentNode;
    }
    
    /**
     * Connects the replacer to the replacee's parent node. In other words,
     * replaces the replacee with the replacer in terms of parent connections
     * only. 
     * 
     * @param replacee The node we are replacing.
     * @param replacer The node we are replacing with.
     */
    private void replaceChildNode( Node<T> replacee, Node<T> replacer ) {
        Node<T> parentNode = replacee.getParentNode();
        if ( replacee == rootNode ) {
            rootNode = replacer;
            
        } else {
            
            if ( parentNode.getChildNode(LESSER_CHILD_NODE_INDEX) == replacee) {
                parentNode.setChildNode( LESSER_CHILD_NODE_INDEX, replacer );
                
            } else {
                parentNode.setChildNode( GREATER_CHILD_NODE_INDEX, replacer );
            }
        }
        
        if ( replacer != null ) {
            replacer.setParentNode( parentNode );
        }
    }
    
    /**
     * Finds and deletes the object in the tree with the same key as dataObject.
     * 
     * @param dataObject A dataObject with the same key as the object you are
     * trying to delete. 
     * @throws InvalidValueException if the dataObject is null or not found
     */
    public void deleteDataObject( T dataObject ) throws InvalidValueException {
        Node<T> node = findNode( dataObject );
        
        if ( node == null ) {
            String errMsg = "The data object was not found in the tree.";
            throw new InvalidValueException( Severity.NON_FATAL, errMsg );
        }
        
        if ( (node.getChildNode( LESSER_CHILD_NODE_INDEX ) == null) &&
             (node.getChildNode( GREATER_CHILD_NODE_INDEX  ) == null) ) {
            replaceChildNode( node, null );
        } else if ( node.getChildNode( LESSER_CHILD_NODE_INDEX ) == null ) {
            replaceChildNode( node, 
                                node.getChildNode( GREATER_CHILD_NODE_INDEX ) );
        } else if ( node.getChildNode( GREATER_CHILD_NODE_INDEX ) == null ) {
            replaceChildNode( node, 
                                node.getChildNode( LESSER_CHILD_NODE_INDEX ) );
        } else {
            Node<T> successorNode = getSuccessorNode( node );
            replaceChildNode( node, successorNode );
            int childNodeIndex = -1;
            Node<T> childNode = null;
            
            for ( int i = 0; i < NUM_CHILD_NODES; i++ ) {
                childNodeIndex = CHILD_NODE_INDECES[i];
                childNode = node.getChildNode( childNodeIndex );
                successorNode.setChildNode( childNodeIndex, childNode );
                
                if ( childNode != null ) {
                    childNode.setParentNode( successorNode );
                }
            }
        }
    }
}
